package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-multiplication-score/
 * @create 2025/9/3 22:06
 * @since JDK17
 */

public class Solution64 {
    long [][] dp;
    public long f(int i, int j, int[]a, int[]b) {
        if (i < 0) {    // 选完了
            return 0;
        }
        if (j < 0) {    // i没选完，j选完了
            return Long.MAX_VALUE / 2;
        }
        if (dp[i][j] != Long.MIN_VALUE) {
            return dp[i][j];
        }
        dp[i][j] = Math.max(f(i, j - 1, a, b), f(i - 1, j - 1, a, b) + (long)a[i] * b[j]);
        return dp[i][j];
    }

    public long maxScore(int[] a, int[] b) {
        int n = b.length;
        dp = new long[4][n];
        for (int i = 0; i < 4; i++) {
            Arrays.fill(dp[i], Long.MIN_VALUE);
        }
        return f(3, n - 1, a, b);
    }
}
